|
In graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. The name is an acronym of the names of people who discovered it: de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. == Precise statement == Let ''G'' = (''V'', ''E'') be a directed graph. An Eulerian circuit is a directed closed path which visits each edge exactly once. In 1736, Euler showed that ''G'' has an Eulerian circuit if and only if ''G'' is connected and the indegree is equal to outdegree at every vertex. In this case ''G'' is called Eulerian. We denote these in- and out-degree of a vertex ''v'' by deg(''v''). The BEST theorem states that the number ec(''G'') of Eulerian circuits in a connected Eulerian graph ''G'' is given by the formula : Here ''t''''w''(''G'') is the number of arborescences, which are trees directed towards the root at a fixed vertex ''w'' in ''G''. The number ''tw(G)'' can be computed as a determinant, by the version of the matrix tree theorem for directed graphs. It is a property of Eulerian graphs that ''t''''v''(''G'') = ''t''''w''(''G'') for every two vertices ''v'' and ''w'' in a connected Eulerian graph ''G''. == Applications == The BEST theorem shows that the number of Eulerian circuits in directed graphs can be computed in polynomial time, a problem which is #P-complete for undirected graphs.〔Brightwell and Winkler, "(Note on Counting Eulerian Circuits )", CDAM Research Report LSE-CDAM-2004-12, 2004.〕 It is also used in the asymptotic enumeration of Eulerian circuits of complete and complete bipartite graphs.〔Brendan McKay and Robert W. Robinson, (Asymptotic enumeration of eulerian circuits in the complete graph ), ''Combinatorica'', 10 (1995), no. 4, 367–377.〕〔M.I. Isaev, (Asymptotic number of Eulerian circuits in complete bipartite graphs ) (in Russian), Proc. 52-nd MFTI Conference (2009), Moscow.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「BEST theorem」の詳細全文を読む スポンサード リンク
|